package com.tgy.algorithm._经典题目01;

/**
 * 背包容量为w
 * 一共有n袋零食,第i袋零食体积为v[i]
 * 总体积不超过背包容量的情况下，一共有多少种零食放法?(总体积为0也算一种放法)。
 */
public class _016_零食问题 {

    public static int snackPacket(int[] nums,int w) {

        return doSnackPacket(nums,0,w);
    }

    public static int doSnackPacket(int[] nums,int index,int rest) {

        if (index == nums.length) {
            return rest == 0 ? 1:0;
        }

        int value = doSnackPacket(nums,index + 1,rest);
        int add = 0;
        if (rest - nums[index] >= 0) {
            add = doSnackPacket(nums, index + 1, rest - nums[index]);
        }
        return value + add;
    }



    public static void main(String[] args) {
        int[] nums = {2,3,4,2,5};
        int count = snackPacket(nums, 8);
        System.out.println(count);
    }
}
